class Solution:
    def getSteps(self, cur: int, n: int) -> int:
        steps, first, last = 0, cur, cur
        while first <= n:
            steps += min(last, n) - first + 1
            first *= 10
            last = last * 10 + 9
        return steps

    def findKthNumber(self, n: int, k: int) -> int:
        cur = 1
        k -= 1
        while k:
            steps = self.getSteps(cur, n)
            if steps <= k:
                k -= steps
                cur += 1
            else:
                cur *= 10
                k -= 1
        return cur


class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        def getCnt(prefix, n):
            cnt, cur, next = 0, prefix, prefix + 1
            while cur <= n:
                cnt += min(next, n + 1) - cur
                cur, next = cur * 10, next * 10
            return cnt

        poi, prefix = 1, 1
        while poi < k:
            cnt = getCnt(prefix, n)
            if poi + cnt > k:
                prefix *= 10
                poi += 1
            else:
                prefix += 1
                poi += cnt
        return prefix

